package B刷题.二叉树;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 剑指 Offer 37. 序列化二叉树
 * @date 2022年11月14日 17:24
 */
public class Code09_SerializeDeserialize {

    public String serialize(TreeNode root) {
        String result = "[";
        LinkedList<TreeNode> list = new LinkedList<>();
        if (root != null) {
            list.add(root);
            result += root.val;
        }
        while (!list.isEmpty()) {
            TreeNode pop = list.pop();
            if (pop.left != null) {
                result += "," + pop.left.val;
                list.add(pop.left);
            } else {
                result += "," + "null";
            }
            if (pop.right != null) {
                result += "," + pop.right.val;
                list.add(pop.right);
            } else {
                result += "," + "null";
            }
        }
        result += "]";
        return result;
    }

    public TreeNode deserialize(String data) {
        data = data.substring(1, data.length() - 1);
        if (data.length() == 0) {
            return null;
        }
        String[] strings = data.split(",");
        LinkedList<String> valueList = new LinkedList<>();
        for (int i = 1; i < strings.length; i++) {
            valueList.add(strings[i]);
        }
        TreeNode head = new TreeNode(Integer.valueOf(strings[0]));
        LinkedList<TreeNode> nodeList = new LinkedList<>();
        nodeList.add(head);
        while (!valueList.isEmpty()) {
            TreeNode pop = nodeList.pop();
            String value1 = valueList.pop();
            if (!value1.equals("null")) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(value1));
                pop.left = treeNode;
                nodeList.add(treeNode);
            }
            String value2 = valueList.pop();
            if (!value2.equals("null")) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(value2));
                pop.right = treeNode;
                nodeList.add(treeNode);
            }
        }
        return head;
    }

}
